package com.cet.qz.unit01.chapter1_3;

import edu.princeton.cs.algs4.StdIn;

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @program: algorithm
 * @description: 中缀表达式转后缀表达式
 * @author: 陈恩涛
 * @create: 2021-04-04 21:48
 **/
public class QZ1_3_10 {

    /**
     *方法描述：比较两个操作符的优先级
     *
     * @param op1
     * @param op2
     * @return int  返回-1则op1优先级小于op2,返回1则op1优先级等于op2,返回0则优先级相等
     * @author chenentao
     * @date 2021/4/6 9:40
     */
    public static int comparePriority(String op1, String op2) {
        List<String> opList = Stream.of("+", "-", "","*", "/").collect(Collectors.toList());
        if (opList.indexOf(op1) - opList.indexOf(op2) <= -2) {
            return -1;
        } else if (opList.indexOf(op1) - opList.indexOf(op2) >= 2) {
            return 1;
        } else {
            return 0;
        }
    }

    /**
     *方法描述： 中缀表达式是否为严格的含括号的表达式，对应不同的逻辑处理
     *
     * @param infixExpression
     * @param flag
     * @return java.lang.String
     * @author chenentao
     * @date 2021/4/4 22:29
     */
    public static void infixToPostfix(String infixExpression,boolean flag) {
        if (flag) {

            //严格含括号的中缀表达式最简单

            Stack<String> ops = new Stack<>();
            for (int i = 0; i < infixExpression.length(); i++) {
                String s = infixExpression.substring(i, i + 1);
                if ("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s)) {
                    ops.push(s);
                } else if (")".equals(s)) {
                    System.out.print(ops.pop());
                } else if ("(".equals(s)) {

                } else {
                    System.out.print(s);
                }
            }
        } else {

            //不要求严格含括号的中缀表达式   a+b*c+(d*e+f)*g

            /*
            * 1、从左到右扫描，遇到操作数直接输出
            * 2、当遇到操作符时
            *       1）当栈为空时，操作符入栈
            *       2）如果该操作符优先级大于等于栈顶操作符的优先级，则该操作符入栈
            *       3）如果该操作符优先级小于栈顶操作符的优先级，则栈顶操作符连续出栈并输出，直到栈顶操作符优先级小于该操作符，该操作符入栈
            *       4）遇到(则入栈，(只有遇到)才出栈
            *       5）遇到），栈顶操作符连续出栈并输出，直到遇到(
            * 3、当表达式扫描完后，栈中依然有操作符，则直接将栈中的操作符出栈并输出
            *
            * */

            Stack<String> stack = new Stack<>();

            for (int i = 0; i < infixExpression.length(); i++) {
                String s = infixExpression.substring(i, i + 1);
                if ("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s)) {
                    if (stack.isEmpty()) {
                        //栈空，操作符入栈
                        stack.push(s);
                    } else if ("(".equals(stack.peek())) {
                        stack.push(s);
                    } else if (comparePriority(s, stack.peek()) == 1) {
                        //扫描到的操作符优先级大于等于栈顶操作符，入栈
                        stack.push(s);
                    } else if (comparePriority(s, stack.peek()) == -1) {
                        //扫描到的操作符优先级小于栈顶操作符
                        do {
                            System.out.print(stack.pop());
                        } while (!stack.isEmpty() && comparePriority(s, stack.peek()) != 1 && !"(".equals(stack.peek()));
                        stack.push(s);
                    }
                } else if ("(".equals(s)) {
                    stack.push(s);
                } else if(")".equals(s)){
                    while (!"(".equals(stack.peek())) {
                        System.out.print(stack.pop());
                    }
                    stack.pop();
                }else  {
                    //遇到操作数直接输出
                    System.out.print(s);
                }
            }

            //扫描结束，栈不为空，栈中操作符出栈并输出
            if (!stack.isEmpty()) {
                for (String s : stack) {
                    System.out.print(s);
                }
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("请输入一个中缀表达式：");
        String expression = StdIn.readString();
        infixToPostfix(expression,false);
    }
}
